// code.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <ilcplex/cplex.h>
#include <iostream>
#include <math.h>
#include <string>
#include "sort.h"

using namespace std;

int nCut1 = 0;

struct matrix {
	int 	scenario;
	int		numcols;
	int 	numrows;
	int 	*rmatind;
	int		*rmatbeg;
	double 	*rmatval;
	double 	**rhs;
	double	*colobj;
};

struct mixInfo {
	int 	p;
	int 	ssize;
	int		zsize;
	int 	*scol;
	int		*zcol;
	int		**rcol;
	int		**idx;  // idx[i][0] is the scenario for row i which has largest right hand side
	double	**rhs;
};

typedef struct matrix MATRIX, *MATRIXptr;
typedef struct mixInfo MIXINFO, *MIXINFOptr;

static int
	getLotSizeMatrix (MATRIXptr matrix, int period, int scenario, int seed);

static int
	BuildModel (CPXENVptr env, CPXLPptr lp, MATRIXptr matrix, MIXINFOptr mixinfo, int flag, double pct);

static int CPXPUBLIC
	blcutcallback (CPXCENVptr env, void	*cbdata, int wherefrom,	void *cbhandle,	int	*useraction_p);
/*
int _tmain(int argc, _TCHAR* argv[])
{
	int status = 0;

	double pct=0.4;

	MATRIX matrix;
	MIXINFO mixinfo;

	//status = getLotSizeMatrix(&matrix,50,320,1291);
	//status = getLotSizeMatrix(&matrix,50,320,121757);
	status = getLotSizeMatrix(&matrix,500,12,13131);

	CPXENVptr	env = NULL;
	CPXLPptr	lp  = NULL;
	env 	= CPXopenCPLEX(&status);
	status 	= CPXsetintparam (env, CPX_PARAM_SCRIND, CPX_ON);
	lp 		= CPXcreateprob (env, &status, "myProb");

	BuildModel(env,lp,&matrix,&mixinfo,1,pct);
	status = CPXwriteprob (env, lp, "ccmip.lp", NULL);
	cout << "-------------------" << endl;
	cout << "solving ccmip ..." << endl;
	cout << "-------------------" << endl;

	status = CPXsetintparam (env, CPX_PARAM_PRELINEAR, CPX_OFF);
	status = CPXsetintparam (env, CPX_PARAM_MIPCBREDLP, CPX_OFF);
	//status = CPXsetusercutcallbackfunc (env, blcutcallback, &mixinfo);

	status = CPXmipopt(env, lp);
	status = CPXfreeprob (env, &lp);
	status = CPXcloseCPLEX (&env);

	env = NULL;
	lp  = NULL;
	env 	= CPXopenCPLEX(&status);
	status 	= CPXsetintparam (env, CPX_PARAM_SCRIND, CPX_ON);
	lp 		= CPXcreateprob (env, &status, "myProb1");

	BuildModel(env,lp,&matrix,&mixinfo,1,pct);
	status = CPXwriteprob (env, lp, "ccmiblp.lp", NULL);
	free(matrix.rmatind);
	free(matrix.rmatbeg);
	free(matrix.rmatval);
	free(matrix.colobj);
	for (int i=0; i<matrix.scenario; i++)
		free(matrix.rhs[i]);
	free(matrix.rhs);
	cout << "-------------------" << endl;
	cout << "solving ccmiblp ..." << endl;
	cout << "-------------------" << endl;

	status = CPXsetintparam (env, CPX_PARAM_PRELINEAR, CPX_OFF);
	status = CPXsetintparam (env, CPX_PARAM_MIPCBREDLP, CPX_OFF);
	status = CPXsetusercutcallbackfunc (env, blcutcallback, &mixinfo);

	status = CPXmipopt(env, lp);

	//double *x = NULL;
	//double objval;
	//int    solstat, surplus;
	//int numcols = CPXgetnumcols(env, lp);
	//char	**colname = NULL;
	//char	*colnamestore = NULL;
	//int		colnamespace;
	//status = CPXgetcolname (env, lp, NULL, NULL, 0, &surplus, 0, numcols-1);
	//colnamespace = - surplus;
	//colname      = (char **) malloc (sizeof(char *)*numcols);
	//colnamestore = (char *)  malloc (colnamespace);
	//status = CPXgetcolname (env, lp, colname, colnamestore, colnamespace, &surplus, 0, numcols-1);
	//x = (double*) malloc(numcols*sizeof(double));
	//status = CPXsolution (env, lp, &solstat, &objval, x, NULL, NULL, NULL);
	//if ( status ) {
	//  fprintf (stderr, "Failed to obtain solution.\n");
	//  goto TERMINATE;
	//}
	//for (int i=0; i<numcols; i++) {
	//	if (x[i]>0) cout << colname[i]<<"="<<x[i] << " ";
	//}
	//cout << endl;

TERMINATE:

	status = CPXfreeprob (env, &lp);
	status = CPXcloseCPLEX (&env);

	free(mixinfo.scol);
	free(mixinfo.zcol);
	for (int i=0; i<mixinfo.ssize; i++)
		free(mixinfo.rhs[i]);
	free(mixinfo.rhs);
	for (int i=0; i<mixinfo.ssize; i++)
		free(mixinfo.idx[i]);
	free(mixinfo.idx);
	for (int i=0; i<mixinfo.ssize; i++)
		free(mixinfo.rcol[i]);
	free(mixinfo.rcol);

	system("pause");
	return status;
}
*/


int _tmain(int argc, _TCHAR* argv[])
{
	int status = 0;

	double pct=0.4;

	MATRIX matrix;
	MIXINFO mixinfo;

	//status = getLotSizeMatrix(&matrix,50,320,1291);
	//status = getLotSizeMatrix(&matrix,50,320,121757);
	status = getLotSizeMatrix(&matrix,500,12,13131);

	CPXENVptr	env = NULL;
	CPXLPptr	lp  = NULL;
	env 	= CPXopenCPLEX(&status);
	status 	= CPXsetintparam (env, CPX_PARAM_SCRIND, CPX_ON);
	lp 		= CPXcreateprob (env, &status, "myProb");

	BuildModel(env,lp,&matrix,&mixinfo,2,pct);
	status = CPXwriteprob (env, lp, "test.lp", NULL);

	status = CPXsetintparam (env, CPX_PARAM_PRELINEAR, CPX_OFF);
	status = CPXsetintparam (env, CPX_PARAM_MIPCBREDLP, CPX_OFF);
	status = CPXsetusercutcallbackfunc (env, blcutcallback, &mixinfo);

	status = CPXmipopt(env, lp);
	
TERMINATE:

	status = CPXfreeprob (env, &lp);
	status = CPXcloseCPLEX (&env);

	free(mixinfo.scol);
	free(mixinfo.zcol);
	for (int i=0; i<mixinfo.ssize; i++)
		free(mixinfo.rhs[i]);
	free(mixinfo.rhs);
	for (int i=0; i<mixinfo.ssize; i++)
		free(mixinfo.idx[i]);
	free(mixinfo.idx);
	for (int i=0; i<mixinfo.ssize; i++)
		free(mixinfo.rcol[i]);
	free(mixinfo.rcol);

	system("pause");
	return status;
}



static int CPXPUBLIC
	blcutcallback (CPXCENVptr env, void	*cbdata, int wherefrom,	void *cbhandle,	int	*useraction_p)
{
	int status = 0;

	int *cutind, numcols, cutnz, tempint, surplus, k, cnt;

	double *x, *cutval, tempsum, temp, temp1, temp2, cutrhs, cutvio;

	MIXINFOptr mixinfo = (MIXINFOptr) cbhandle;

	int scenario=mixinfo->zsize;

	*useraction_p = CPX_CALLBACK_DEFAULT;

	CPXCLPptr lp;
	status = CPXgetcallbacklp (env, cbdata, wherefrom, &lp);
	numcols = CPXgetnumcols(env, lp);

	//char	**colname = NULL;
	//char	*colnamestore = NULL;
	//int		colnamespace;

	//status = CPXgetcolname (env, lp, NULL, NULL, 0, &surplus, 0, numcols-1);
	//colnamespace = - surplus;
	//colname      = (char **) malloc (sizeof(char *)*numcols);
	//colnamestore = (char *)  malloc (colnamespace);
	//status = CPXgetcolname (env, lp, colname, colnamestore, colnamespace, &surplus, 0, numcols-1);

	x  = (double*) malloc (numcols*sizeof(double));
	status = CPXgetcallbacknodex  (env, cbdata, wherefrom, x, 0, numcols-1);

	cutind = (int*) malloc(numcols*sizeof(int));
	cutval = (double*) malloc(numcols*sizeof(double));
if (nCut1>=1) goto TERMINATE;
	for (int i=0; i<mixinfo->ssize; i++) {
		tempsum=0.0;
		cutnz=0;
		cutrhs = 0.0;
		cutvio = cutrhs;
		cutind[cutnz] = mixinfo->zcol[mixinfo->idx[i][0]];
		cutval[cutnz] = 1;
		//cutvio -= x[cutind[cutnz]]*cutval[cutnz];
		cutnz++;
		cnt=1;
		//for (int j=scenario; j>mixinfo->p; j--) {
		for (int j=mixinfo->p; j<scenario; j++) {
			/*temp = x[mixinfo->rcol[i][mixinfo->idx[i][j]]] - mixinfo->rhs[i][mixinfo->idx[i][0]]*x[mixinfo->zcol[mixinfo->idx[i][j]]];
			if (temp<0) {*/
				temp1 = 1.0/(mixinfo->rhs[i][mixinfo->idx[i][0]]- mixinfo->rhs[i][mixinfo->idx[i][mixinfo->p-cnt]]);

				if (cnt==1) {
					temp2 = temp1;
				}
				else {
					temp1=temp1-tempsum;
					temp2 = temp1<temp2? temp1:temp2;
				}
				if (temp2<=0) break;
				tempsum+=temp2;
				
				cutind[cutnz] = mixinfo->rcol[i][mixinfo->idx[i][j]];
				cutval[cutnz] = temp2;
				//cutvio -= x[cutind[cutnz]]*cutval[cutnz];
				cutnz++;

				cutind[cutnz] = mixinfo->zcol[mixinfo->idx[i][j]];
				cutval[cutnz] = -temp2*mixinfo->rhs[i][mixinfo->idx[i][0]];
				//cutvio -= x[cutind[cutnz]]*cutval[cutnz];
				cutnz++;
				cnt++;
			//}

			if (mixinfo->rhs[i][mixinfo->idx[i][0]] == mixinfo->rhs[i][mixinfo->idx[i][mixinfo->p-cnt]]) break;		
		}

		if (/*cutvio>0.01*/1) {
			//nCut1++;
			//if (nCut1>4) break;
			//if (nCut1==5) {
			//for (int j=0; j<cutnz-1; j++) {
			//	if (cutval[j] != 0) printf("%f %s ", cutval[j],colname[cutind[j]]);
			//	if (cutval[j+1]>0) printf("+");
			//}
			//printf("%f %s ", cutval[cutnz-1],colname[cutind[cutnz-1]]); cout <<">="<<cutrhs << endl;
			//}

			//for (int j=0; j<cutnz; j++) {
			//	printf("%f %d", cutval[j],cutind[j]);
			//}
			//cout << "cutvio=" << cutvio <<endl;
	
			status = CPXcutcallbackadd (env, cbdata, wherefrom, cutnz, cutrhs, 'G', cutind, cutval,0);
			if ( status ) {
				fprintf (stderr, "Failed to add cut.\n");
				goto TERMINATE;
			}
			nCut1++;
		}
	}

	*useraction_p = CPX_CALLBACK_SET;

TERMINATE:
	free(cutind);
	free(cutval);
	free(x);

	return status;
}

static int getLotSizeMatrix (MATRIXptr matrix, int period, int scenario, int seed)
{
	int status = 0;

	int nzcnt;

	srand(seed);

	matrix->scenario = scenario;
	matrix->numrows = period;
	matrix->numcols = period;

	matrix->rmatbeg = (int*) malloc((matrix->numrows+1)*sizeof(int));
	matrix->rmatind = (int*) malloc(matrix->numrows*matrix->numcols*sizeof(int));
	matrix->rmatval = (double*) malloc(matrix->numrows*matrix->numcols*sizeof(double));

	matrix->rmatbeg[0]=0; nzcnt=0;
	for (int i=0; i<matrix->numrows; i++) {
		for (int j=0; j<=i; j++) {
			matrix->rmatind[nzcnt] = j;
			matrix->rmatval[nzcnt] = 1;
			nzcnt++;
		}
		matrix->rmatbeg[i+1] = nzcnt;
	}

	matrix->rhs = (double**) malloc(scenario*sizeof(double));
	for (int i=0; i<scenario; i++)
		matrix->rhs[i] = (double*) malloc(matrix->numrows*sizeof(double));

	matrix->colobj = (double*) malloc(matrix->numcols*sizeof(double));

	for (int i=0; i<period; i++) {
		for (int j=0; j<scenario; j++) {
			if (i==0) {
				matrix->rhs[j][i] = rand() % 19 + 1;
			}
			else {
				matrix->rhs[j][i] = rand() % 19 + 1 + matrix->rhs[j][i-1];
			}
		}
	}

	for (int i=0; i<matrix->numcols; i++) {
		matrix->colobj[i] = rand() % 10;
	}

//	for (int i=0; i<matrix->numrows; i++) {
//		for (int j=matrix->rmatbeg[i]; j<matrix->rmatbeg[i+1]; j++) {
//			cout << "(" << matrix->rmatind[j] << "," << matrix->rmatval[j] <<")";
//		}
//		cout << endl;
//	}

	return status;
}

static int BuildModel (CPXENVptr env, CPXLPptr lp, MATRIXptr matrix, MIXINFOptr mixinfo, int flag, double pct)
{
	int status = 0;

	int scenario = matrix->scenario;
	int *rmatind, *xcol, *idx, i, j, numcols=0, nzcnt, zero=0, p;

	double *rmatval, *temp, colobj, rhs, inf=CPX_INFBOUND;

	char *colname, *rowname, vch, sense;

	string s;

	CPXchgobjsen (env, lp, CPX_MIN);

	p = (int) floor(pct*scenario);
	mixinfo->p=p;

	xcol = (int*) malloc(matrix->numcols*sizeof(int));
	mixinfo->scol = (int*) malloc(matrix->numrows*sizeof(int));
	mixinfo->zcol = (int*) malloc(scenario*sizeof(int));
	mixinfo->rcol = (int**) malloc(matrix->numrows*sizeof(int));
	for (i=0; i<matrix->numrows; i++)
		mixinfo->rcol[i] = (int*) malloc(scenario*sizeof(int));

	colname = (char*) malloc(30*sizeof(char));
	for (i=0; i<matrix->numcols; i++) {
		s = "x_" + to_string(i);
		colname = (char*) s.c_str();
		colobj = matrix->colobj[i];
		vch='C';
		status = CPXnewcols(env, lp, 1, &colobj, NULL, NULL, &vch, &colname);
		xcol[i] = numcols;
		numcols++;
	}
	for (i=0; i<matrix->numrows; i++) {
		s = "s_" + to_string(i);
		colname = (char*) s.c_str();
		colobj=0;
		vch='C';
		status = CPXnewcols(env, lp, 1, &colobj, NULL, NULL, &vch, &colname);
		mixinfo->scol[i] = numcols;
		numcols++;
	}
	for (i=0; i<scenario; i++) {
		s = "z_" + to_string(i);
		colname = (char*) s.c_str();
		colobj=0;
		vch='B';
		status = CPXnewcols(env, lp, 1, &colobj, NULL, NULL, &vch, &colname);
		mixinfo->zcol[i] = numcols;
		numcols++;
	}
	if (flag>=1) {
		for (i=0; i<scenario; i++) {
			for (j=0; j<matrix->numrows; j++) {
				s = "r_" + to_string(j) + "_" + to_string(i);
				colname = (char*) s.c_str();	
				colobj=0;
				vch='C';
				status = CPXnewcols(env, lp, 1, &colobj, NULL, NULL, &vch, &colname);
				mixinfo->rcol[j][i] = numcols;
				numcols++;
			}
		}
	}
	colname = NULL;

	mixinfo->ssize = matrix->numrows;
	mixinfo->zsize = scenario;
	mixinfo->rhs = (double**) malloc(matrix->numrows*sizeof(double));
	mixinfo->idx = (int**) malloc(matrix->numrows*sizeof(int));
	temp = (double*) malloc(scenario*sizeof(double));
	idx = (int*) malloc(scenario*sizeof(int));
	for (int j=0; j<matrix->numrows; j++) {
		mixinfo->rhs[j] = (double*) malloc(scenario*sizeof(double));
		mixinfo->idx[j] = (int*) malloc(scenario*sizeof(int));

		for (int i=0; i<scenario; i++) {
			mixinfo->rhs[j][i] = matrix->rhs[i][j];
			temp[i] = mixinfo->rhs[j][i];
			idx[i] = i;
		}

		quickIdxSort(temp,idx,0,scenario-1,-1);
		for (int i=0; i<scenario; i++) {
			mixinfo->idx[j][i] = idx[i];
		}

//		for (int i=0; i<scenario; i++) {
//			cout << mixinfo->rhs[j][mixinfo->idx[j][i]] << " ";
//		}
//		cout << endl;
	}
	free(temp);

	rowname = (char*) 	malloc(30*sizeof(char));
	rmatind = (int*)  	malloc(numcols*sizeof(int));
	rmatval = (double*) malloc(numcols*sizeof(double));

	for (i=0; i<matrix->numrows; i++) {
		s = "a_" + to_string(i);
		rowname = (char*) s.c_str();
		nzcnt=0;
		for (j=matrix->rmatbeg[i]; j<matrix->rmatbeg[i+1]; j++) {
			rmatind[nzcnt] = matrix->rmatind[j];
			rmatval[nzcnt] = matrix->rmatval[j];
			nzcnt++;
		}
		rmatind[nzcnt] = mixinfo->scol[i];
		rmatval[nzcnt] = -1;
		nzcnt++;
		rhs=0.0;
		sense='E';
		status = CPXaddrows(env, lp, 0, 1, nzcnt, &rhs, &sense, &zero, rmatind, rmatval, NULL, &rowname);
	}

	for (j=0; j<matrix->numrows; j++) {
		for (i=0; i<scenario; i++) {
			s = "m_" + to_string(i) + "_" + to_string(j);
			rowname = (char*) s.c_str();
			nzcnt=0;
			rmatind[nzcnt] = mixinfo->scol[j];
			rmatval[nzcnt] = 1;
			nzcnt++;
			rhs = matrix->rhs[i][j];
			rmatind[nzcnt] = mixinfo->zcol[i];
			rmatval[nzcnt] = rhs;
			nzcnt++;
			if (flag==1) {
				rmatind[nzcnt] = mixinfo->rcol[j][i];
				rmatval[nzcnt] = -1;
				nzcnt++;
			}
			sense='G';
			status = CPXaddrows(env, lp, 0, 1, nzcnt, &rhs, &sense, &zero, rmatind, rmatval, NULL, &rowname);
		}
	}

	rhs=p;
	nzcnt=0;
	s = "card";
	rowname = (char*) s.c_str();
	for (i=0; i<scenario; i++) {
		rmatind[nzcnt] = mixinfo->zcol[i];
		rmatval[nzcnt] = 1;
		nzcnt++;
	}
	sense = 'L';
	status = CPXaddrows(env, lp, 0, 1, nzcnt, &rhs, &sense, &zero, rmatind, rmatval, NULL, &rowname);

	if (flag>=1) {
		temp = (double*) malloc(scenario*sizeof(double));
		for (j=0; j<matrix->numrows; j++) {
			for (i=0; i<scenario; i++) temp[i] = matrix->rhs[i][j];
			quickSort(temp,0,scenario-1,-1);
			for (i=0; i<scenario; i++) {
				s = "m1_" + to_string(i) + "_" + to_string(j);
				rowname = (char*) s.c_str();
				nzcnt=0;
				rhs = 0;
				if (i<p) {
					rmatind[nzcnt] = mixinfo->zcol[mixinfo->idx[j][i]];
					rmatval[nzcnt] = -temp[p];
					nzcnt++;
					rmatind[nzcnt] = mixinfo->rcol[j][mixinfo->idx[j][i]];
					rmatval[nzcnt] = 1;
					nzcnt++;
				}
				else {
					rmatind[nzcnt] = mixinfo->zcol[mixinfo->idx[j][i]];
					rmatval[nzcnt] = -temp[p-1];
					nzcnt++;
					rmatind[nzcnt] = mixinfo->rcol[j][mixinfo->idx[j][i]];
					rmatval[nzcnt] = 1;
					nzcnt++;
				}
				sense='G';
				status = CPXaddrows(env, lp, 0, 1, nzcnt, &rhs, &sense, &zero, rmatind, rmatval, NULL, &rowname);
			}
		}

		free(temp);

		if (flag>=2) {
		for (int i=0; i<mixinfo->ssize; i++) {
			double tempsum = 0.0;
			nzcnt = 0;
			rhs = 0;
			rmatind[nzcnt] = mixinfo->zcol[mixinfo->idx[i][0]];
			rmatval[nzcnt] = 1;
			nzcnt++;
			int cnt=1;
			double temp1,temp2;
			for (int j=mixinfo->p; j<scenario; j++) {
				temp1 = 1.0/(mixinfo->rhs[i][mixinfo->idx[i][0]]- mixinfo->rhs[i][mixinfo->idx[i][mixinfo->p-cnt]]);

				if (cnt==1) {
					temp2 = temp1;
				}
				else {
					temp1=temp1-tempsum;
					temp2 = temp1<temp2? temp1:temp2;
				}
				if (temp2<=0) break;
				tempsum+=temp2;

				rmatind[nzcnt] = mixinfo->rcol[i][mixinfo->idx[i][j]];
				rmatval[nzcnt] = temp2;
				nzcnt++;

				rmatind[nzcnt] = mixinfo->zcol[mixinfo->idx[i][j]];
				rmatval[nzcnt] = -temp2*mixinfo->rhs[i][mixinfo->idx[i][0]];
				nzcnt++;
				cnt++;
				if (mixinfo->rhs[i][mixinfo->idx[i][0]] == mixinfo->rhs[i][mixinfo->idx[i][mixinfo->p-cnt]]) break;
			}
			sense='G';

			status = CPXaddrows(env, lp, 0, 1, nzcnt, &rhs, &sense, &zero, rmatind, rmatval, NULL, NULL);
		}
		}
	}

	free(rmatind);
	free(rmatval);

	free(xcol);
	return status = 0;
}
